package main

import "fmt"

func main() {
	arr := []int{5, 7, 7, 8, 8, 10}
	res := searchRange(arr, 6)
	fmt.Println(res)
}

func searchRange(nums []int, target int) []int {
	min, max := -1, -1
	l, r := 0, len(nums)-1

	// 先查询
	for l <= r {
		mid := l + ((r - l) >> 1)
		if target == nums[mid] {
			if mid < min || min == -1 {
				min = mid
			}
			r = mid - 1 // 这里很关键
		} else if target > nums[mid] { // 在右边
			l = mid + 1
		} else {
			r = mid - 1
		}
	}

	// 再查询最大的
	l, r = 0, len(nums)-1
	for l <= r {
		mid := l + ((r - l) >> 1)
		if target == nums[mid] {
			if mid > max  || min == -1 {
				max = mid
			}
			l = mid + 1  // 这里很关键
		} else if target > nums[mid] { // 在右边
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return []int{min, max}
}
